2010년07월24일 4번
[과목 구분 없음] 해시(hash) 탐색에서 제산법(division)은 키(key) 값을 배열(array)의 크기로 나누어 그 나머지 값을 해시 값으로 사용하는 방법이다. 다음 데이터의 해시 값을 제산법으로 구하여 11개의 원소를 갖는 배열에 저장하려고 한다. 해시 값의 충돌(collision)이 발생하는 데이터를 열거해 놓은 것은?
- ① 111, 112
- ② 112, 222
- ③ 113, 221
- ④ 220, 222
(정답률: 69%)
문제 해설
제산법으로 해시 값을 구할 때, 키 값을 배열의 크기로 나눈 나머지 값을 해시 값으로 사용한다. 이 문제에서는 배열의 크기가 11이므로, 각 데이터의 키 값을 11로 나눈 나머지 값을 구하면 된다.
- 111을 11로 나눈 나머지는 1
- 112를 11로 나눈 나머지는 1
- 113을 11로 나눈 나머지는 2
- 220을 11로 나눈 나머지는 9
- 222을 11로 나눈 나머지는 0
- 221을 11로 나눈 나머지는 10
위 결과를 보면, 112와 222는 모두 해시 값이 1이 되므로 충돌이 발생한다. 따라서 정답은 "112, 222"이다.
- 111을 11로 나눈 나머지는 1
- 112를 11로 나눈 나머지는 1
- 113을 11로 나눈 나머지는 2
- 220을 11로 나눈 나머지는 9
- 222을 11로 나눈 나머지는 0
- 221을 11로 나눈 나머지는 10
위 결과를 보면, 112와 222는 모두 해시 값이 1이 되므로 충돌이 발생한다. 따라서 정답은 "112, 222"이다.
